package com.lw.leetcode.other.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 139. 单词拆分
 *
 * @Author liw
 * @Date 2021/4/29 15:24
 * @Version 1.0
 */
public class WordBreak {

    public static void main(String[] args) {
        WordBreak wordBreak = new WordBreak();

        List<String> wordDict = new ArrayList<String>(){{
            add("apple");
            add("pen");
        }};

        boolean applepenapple = wordBreak.wordBreak("applepenapplea", wordDict);
        System.out.println(applepenapple);
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int size = wordDict.size();
        Map<String, Integer> map = new HashMap<>(size << 1);
        for (String str : wordDict) {
            map.put(str, 1);
        }
        int length = s.length();
        boolean[] arr = new boolean[length];
        for (int i = 0; i < length; i++) {
            String sub = s.substring(0, i + 1);
            if (map.get(sub) != null) {
                arr[i] = true;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j]) {
                        sub = s.substring(j + 1, i + 1);
                        if (map.get(sub) != null) {
                            arr[i] = true;
                            break;
                        }
                    }
                }
            }
        }
        return arr[length - 1];
    }

}
